package leetcode.problems.P85最大矩形;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class MaximalRectangle {
}

//class Solution {
//    int m, n;
//
//    public int maximalRectangle(char[][] matrix) {
//        m = matrix.length;
//        if (m < 1) {
//            return 0;
//        }
//        n = matrix[0].length;
//        int[][] left = new int[m][n]; // 计算left数组
//        for (int i = 0; i < m; ++i) {
//            left[i][0] = matrix[i][0] != '0' ? 1 : 0;
//            for (int j = 1; j < n; ++j) {
//                if (matrix[i][j] != '0') {
//                    left[i][j] = left[i][j - 1] + 1;
//                }
//            }
//        }
//        int maxArea = 0, rowCnt, minWidth;
//        for (int k = m - 1; k >= 0; --k) {
//            for (int j = n - 1; j >= 0; --j) {
//                rowCnt = 0;
//                minWidth = Integer.MAX_VALUE;
//                for (int i = k; i >= 0; --i) { // 选定第j列，往上遍历left第j列
//                    if (left[i][j] != 0) {
//                        minWidth = Math.min(minWidth, left[i][j]);
//                        rowCnt++;
//                    } else {
//                        rowCnt = 0;
//                        minWidth = Integer.MAX_VALUE;
//                    }
//                    maxArea = Math.max(maxArea, rowCnt * minWidth);
//                }
//            }
//        }
//        return maxArea;
//    }
//}

// 单调栈+前缀数组
class Solution {
    int m, n;

    public int maximalRectangle(char[][] matrix) {
        m = matrix.length;
        if (m < 1) {
            return 0;
        }
        n = matrix[0].length;
        int[][] leftAcc = new int[m][n]; // 计算leftAcc数组
        for (int i = 0; i < m; ++i) {
            leftAcc[i][0] = matrix[i][0] != '0' ? 1 : 0;
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] != '0') {
                    leftAcc[i][j] = leftAcc[i][j - 1] + 1;
                }
            }
        }
        int maxArea = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int j = n - 1; j >= 0; --j) {
            int[] down = new int[m], upper = new int[m];
            for (int k = m - 1; k >= 0; --k) {// 从下往上，往下“看”
                while (!stack.isEmpty() && leftAcc[stack.peekLast()][j] >= leftAcc[k][j]) {
                    stack.pollLast();
                }
                down[k] = stack.isEmpty() ? m - 1 : stack.peekLast() - 1;
                stack.addLast(k);
            }
            stack.clear();
            for (int k = 0; k < m; ++k) {// 从上往下，往上“看”
                while (!stack.isEmpty() && leftAcc[stack.peekLast()][j] >= leftAcc[k][j]) {
                    stack.pollLast();
                }
                upper[k] = stack.isEmpty() ? 0 : stack.peekLast() + 1;
                stack.addLast(k);
            }
            for (int i = 0; i < m; i++) {
                maxArea = Math.max(maxArea, leftAcc[i][j] * (down[i] - upper[i] + 1));
            }
        }
        return maxArea;
    }
}
